package com.cat.dataStructure;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.HashSet;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/3sum/?envType=problem-list-v2&envId=two-pointers
 * @create 2025/8/17 14:37
 * @since JDK17
 */

public class Solution30 {
    static HashSet<List<Integer>> set = new HashSet<>();

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int target = -nums[i];
            for (int l = i + 1, r = n - 1; l < r; ) {
                if (nums[l] + nums[r] > target) {
                    r--;
                } else if (nums[l] + nums[r] < target) {
                    l++;
                } else {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[l++]);
                    list.add(nums[r--]);
                    if (!set.contains(list)) {
                        ans.add(list);
                        set.add(list);
                    }
                }
            }
        }

        return ans;
    }
}
